ZKP Gadgets
$ \gdef\set#1{\mathcal{#1}} $
Binary check
Constrain $a ∈ {0, 1}$:
Constraints:
$$ a ⋅(1 - a) = 0 $$
This is a special case of constraining $a$ to a small set of values $\{c_0, c_1, \dots \}$:
$$ (a - c_0) ⋅(a - c_1) \cdots = 0 $$
Zero check
Given $a$ construct
$$ b = \begin{cases} 0 & a \ne 0 \\ 1 & a = 0 & \end{cases} $$
Constraints:
$$ \begin{aligned} b &= 1 - a ⋅ w & a ⋅ b &= 0 \end{aligned} $$
Witness: $w = a^{-1}$.
Alternatively can inline the definition of $b$:
$$ (1 - a ⋅ w) ⋅ a = 0 $$
Sign check
Multiset equality
Given trace columns of values $\vec v$, $\vec w$ represented as polynomials $V(ω^i) = v_i$, $W(ω^i) = w_i$. We can proof that the multi-set of values in $\vec v$ equals $\vec w$.
$$ \prod_{a ∈ \vec v} ( a + γ ) = \prod_{b ∈ \vec w} ( b + γ ) $$
Range check
https://hackmd.io/D-vjBYtHQB2BuOB-HMUG5Q
Permutation check
https://hackmd.io/@arielg/ByFgSDA7D
Plookup
Given $a$ constrain $a ∈ \set A$.
Read only memory
Given $i$ constrain $a = v_i$ for constant vector $\vec v$.
Use Plookup with
$$ A = \{ i ⋅ c + v_i\} $$
where $c > \max \vec v$ and constrain $a + i ⋅ c ∈ A$.
Alternatively take $v_i ⋅c$, $c > |v|$ and $a ⋅ c + i ∈ A$.
Random access memory
$a = \mathtt{get}(i)$
$\mathtt{set}(i, a)$
The trace is augmented by a $v$ counter that increases (at least) for every RAM operation.
In addition to trace, provide permuted copy of RAM operations such that:
- $i$ (location) is monotonically increasing.
- $v$ (version) is monotonically increasing while $i$ is constant.
- $c$ (contents) is constant unless a $\mathtt{set}$ changes it or $i$ changes.
https://hackmd.io/@bobbinth/HJr56BKKt
Implementation tricks https://zips.z.cash/protocol/canopy.pdf#circuitdesign
